Array multipliers are often used in critical parts of complex digital circuits, such as Digital Signal Processors (DSPs), because of their circuit area and speed. They are often efficiently implemented in Very Large Scale Integration (VLSI) devices if they are built of regular two-dimensional Iterative Logic Arrays (ILAs) and not as tree-like multipliers. Their operation can essentially be divided in two parts. The first is the calculation of a set partial products and the second is the summation of these products to form the final product of the multiplication.
It is widely known to implement such multiplier operations within a data processor by utilizing a multiplier recoding algorithm. The purpose of a recoding algorithm is to reduce the number of addition operations, which determine the partial products required to complete a processor multiplier instruction. A conventional add-shift multiplier operation that has an M-bit multiplicand operand and an N-bit multiplier operand, where M and N are integers, typically requires an N-number of additional operations to complete a processor multiplier instruction. By utilizing a recoding algorithm such as Booth's recoding algorithm or a modified Booth's recoding algorithm, the number of additional operations required to complete the multiplier instruction can be significantly reduced.
A multiplier that utilizes Booth's recoding algorithm is taught by Tokumaru et al in U.S. Pat. No. 4,807,175, entitled "Booth's Multiplier," which is incorporated by reference herein. Tokumaru et al utilize two separate adder units to calculate two separate intermediate partial products, then sum the two separate intermediate partial products with a previously formed full partial product in two additional adder units to calculate each new full partial product.
Because the Booth algorithm uses a special technique to perform multiplication, array multipliers based on it are faster and require less area compared to other types of array multipliers. Both standard array multipliers and modified-Booth array multipliers, due to their highly defined structure, can be efficiently tested, if they are either linear-testable, (i.e. tested with a number of test vectors increasing linearly with the size of the multiplier), or C-testable, (i.e. tested with a constant number of test vectors irrespective to the size of the multiplier). The testability of standard array multipliers has been studied and explained in such publications as, Shen et al, "The Design of Easily Testable VLSI Array Multipliers," IEEE Transaction of Computers, Vol. C-33, No. 6, pp. 554-560, June 1984. In such publications, efficient test sets of either linear or constant size have been extracted and specific Design-For-Testability (DFT) techniques have been known.
A specific example of such a test scheme is taught by Van Meerbergen, et al, U.S. Pat. No. 4,866,715, issued Sep. 12, 1989, which is incorporated by reference herein, wherein it is taught to test a modified Booth multiplier by multiplying an m-bit value X=x(m-1) . . . x(1) x(0), where x(0) is the least-significant bit, by an n-bit value Y=y(n-1) . . . y(1) y(0), where y(0) is the least-significant bit. The Van Meerbergen modified Booth multiplier uses a Booth encoder in which the n-bit value is converted into a series of multiplication values (Y'=y'(k-2) . . . y'(2) y'(0), where k=n if n is even and k=n+1 if n is odd. The conversion occurs in groups of 3 bits, which overlap each time by one bit. The groups of 3 bits take the form y(i-1) y(i) y(i+1), where i=0, 2, 4, . . . n-2, if n is even and i=0, 2, 4, . . . n-1, if n is odd. The bits y(-1) and, if n is odd, y(n) have adjustable values. The Van Meerbergen modified booth multiplier further uses a multiplex circuit for forming partial products (X.y' (j)), and a matrix configuration of full adders for adding the successively obtained partial products in incremental positions. By this method, a number of test patterns are obtained in the modified Booth multiplier on the basis of specifically applied X,Y values. The test patterns produce values, on an output of the modified Booth multiplier, that reveal whether the modified Booth multiplier is defective. For a modified Booth multiplier having a substantial number of bits to be processed, however, the number of feasible test patterns is so large that the Van Meerbergen method of testing is not very efficient and often even impracticable.
Other DFT approaches for modified-Booth multipliers are also found in such publications as Stans, "The Testability of a Modified Booth Multiplier," Proc. Of 1.sup.st European Test Conference ETC '89, pp. 932-942, April 1989; van Sas et al, "Design of a C-testable Booth Multiplier Using a Realistic Fault Model," Journal of Electronic Testing: Theory and Applications," Vol. 5, No. 1, pp. 29-41, February 1994; Waller et al, "A C-testable Parallel Multiplier Using Differential Cascode Voltage Switch (DCVS) Logic," IFIP Transactions A, Vol. A-42, pp. 133-142, 1994; and Gizopoulos et al, "C-testable Multipliers Based on the Modified Booth Algorithm," Proc. 3.sup.rd Asian Test Symposium, pp. 163-168, November 1994.
Most of these publications base their approaches on the assumption that specific implementations of the multiplier cells use either a silicon compiler or a standard DCVS logic. The last publication is based on independent specific implementations of the multiplier cells. DFT modifications are used in the above cited publications to make the multiplier C-testable and provide a small test set regardless of the operands lengths. The test sets of all these publications are meant to be externally stored and applied to the multiplier under test and their output response externally evaluated. The application of these types of approaches to multipliers embedded in complex designs is very difficult due to the low controllability and observability of the multipliers and due to the expense of such approaches in terms of hardware implementation because of the irregularity of both input test sets and their output responses.
Therefore, there exists a need in the art to provide an efficient BIST scheme for embedded multipliers as well as for other embedded structures, such as RAMS, ROMS, FIFOs, etc., so as to allow at-speed testing (i.e. operating system speed), provide very high fault coverage and drive down the cost of testing for the overall circuit. The present invention addresses such a need.